// 构造节点
class Node {
  constructor(key, val) {
    this.key = key
    this.val = val
    this.prev = null
    this.next = null
  }
}
// 构造双向链表
class DoubleList {
  constructor() {
    this.head = new Node(0, 0)
    this.tail = new Node(0, 0)
    this.head.next = this.tail
    this.tail.prev = this.head
    this.size = 0
  }

  addLast (node) {
    node.prev = this.tail.prev
    node.next = this.tail
    this.tail.prev.next = node
    this.tail.prev = node
    this.size++
  }

  remove (node) {
    node.prev.next = node.next
    node.next.prev = node.prev
    this.size--
  }
  // 删除第一个节点并返回
  removeFirst () {
    if (this.head.next === this.tail) {
      return null
    }
    const node = this.head.next
    this.remove(node)
    return node
  }
}

class LRUCache {
  constructor(capacity = 2) {
    // 提升某个Key
    const makeRecently = (key) => {
      const node = this.hashMap.get(key)
      this.cache.remove(node)
      this.cache.addLast(node)
    }
    // 添加最近使用的元素
    const addRecently = (key, val) => {
      const node = new Node(key, val)
      this.hashMap.set(key, node)
      this.cache.addLast(node)
    }
    // 删除某个Key
    const deleteKey = (key) => {
      const node = this.hashMap.get(key)
      this.hashMap.delete(key)
      this.cache.remove(node)
    }
    // 删除长时间未使用的key
    const removeLeastRecently = () => {
      const node = this.cache.removeFirst()
      const key = node.key
      this.hashMap.delete(key)
    }
    this.cap = capacity
    this.hashMap = new Map()
    this.cache = new DoubleList()
    this.get = (key) => {
      if (!this.hashMap.has(key)) {
        return -1
      }
      makeRecently(key)
      return this.hashMap.get(key)
    }
    this.put = (key, val) => {
      if (this.hashMap.has(key)) {
        deleteKey(key)
        addRecently(key, val)
        return
      }
      if (this.cache.size >= this.cap) {
        removeLeastRecently()
      }
      addRecently(key, val)
    }
  }
}

// let List = new DoubleList()
// let node = new Node(1, 1)
// List.addLast(node)
// let firstNode = List.removeFirst(node)
// console.log('firstNode', firstNode)
// console.log('List', List.size)

const luaCache = new LRUCache()
luaCache.put('a', 'aaa')
luaCache.put('b', 'bbb')
luaCache.put('c', 'ccc')


console.log(luaCache.hashMap)

